package 第五周;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author xhw
 */

public class 串联所有的单词的子串 {
    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo", "bar"};
        List<Integer> result = findSubstring(s, words);

        System.out.println("合法的起始位置：" + result);
    }

    private static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> indices = new ArrayList<>();
        if (words.length == 0 || s.length() == 0) return indices;

        int wordLength = words[0].length();
        int allWordsLength = wordLength * words.length;
        if (s.length() < allWordsLength) return indices;

        // 初始化单词的频率计数
        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - allWordsLength; i++) {
            Map<String, Integer> seen = new HashMap<>();

            for (int j = 0; j < words.length; j++) {
                int wordIndex = i + j * wordLength;
                String word = s.substring(wordIndex, wordIndex + wordLength);
                if (!wordCount.containsKey(word)) break;

                seen.put(word, seen.getOrDefault(word, 0) + 1);

                // 如果见过的超过应有的次数，终止内层循环
                if (seen.get(word) > wordCount.get(word)) break;

                // 如果已经到达words数组的长度，说明成功找到一个位置
                if (j + 1 == words.length) indices.add(i);
            }
        }

        return indices;
    }
}
